;(function(window){
	window.QuickSort = {
		sort: function(pDatas){
			this._datas = pDatas;
			this._halfSort(0,pDatas.length-1);
		},
		_partition: function(min, right, pivot){
			var lIdx = min - 1,
				rIdx = right;
			while(true){
				// 左指针不断向右移动，由于pivot在右边界+1的位置，所以，指针最多移动到右边界
				while( this._datas[++lIdx]<pivot);
				while(rIdx > min && this._datas[--rIdx]>pivot);
				if( lIdx >= rIdx ) break;
				else this._swap(lIdx, rIdx);
			}
			this._swap(lIdx, right);
			return lIdx;
		},
		partition: function(pDatas){
			var pivot = pDatas[pDatas.length-1],
				min = 0,
				lIdx = min - 1,
				max = pDatas.length-2,
				rIdx = max + 1;
			while(true){
				while( lIdx < max && pDatas[++lIdx]<pivot);
				while(rIdx > min && pDatas[--rIdx]>pivot);
				if( lIdx >= rIdx ) break;
				else{
					var tmp = pDatas[lIdx];
					pDatas[lIdx] = pDatas[rIdx];
					pDatas[rIdx] = tmp;
				}
			}
		},
		_swap: function(idx1, idx2){
			var tmp = this._datas[idx1];
			this._datas[idx1] = this._datas[idx2];
			this._datas[idx2] = tmp;
		},
		_halfSort: function(left, right){
			if( right - left > 0 ){
				var pivot = this._datas[right];
				var partition = this._partition(left, right, pivot);
				this._halfSort(left, partition-1);
				this._halfSort(partition+1, right);
			}
		}
	};
})(window);